package com.leetcode.Offer;

import java.util.HashMap;
import java.util.Map;

public class JZ38 {//首次编写，这种只适用于非重复字符全排列
    int num = 0;

    public String[] permutation(String s) {
        //全排列
        HashMap<Character, Boolean> ifShow = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            ifShow.put(aChar, false);
        }
        String[] strings = new String[allNum(s.length())];
        dfs(s, strings, new StringBuilder(), ifShow);
        return strings;

    }

    private void dfs(String s, String[] strings, StringBuilder sb, Map<Character, Boolean> ifShow) {
        if (sb.length() == s.length()) {
            strings[num++] = sb.toString();
        }

        for (int i = 0; i < s.length(); i++) {
/*            if (i!=0&&s.charAt(i)==s.charAt(i-1)){
                continue;
            }*/
            if (!ifShow.get(s.charAt(i))) {
                sb.append(s.charAt(i));
                ifShow.put(s.charAt(i), true);
                dfs(s, strings, sb, ifShow);
                sb = sb.deleteCharAt(sb.length() - 1);
                ifShow.put(s.charAt(i), false);
            }

        }
    }

    private int allNum(int num) {
        int sum = 1;
        for (int i = 1; i <= num; i++) {
            sum *= i;
        }
        return sum;
    }

    public static void main(String[] args) {
        for (String abc : new JZ38().permutation("abc")) {
            System.out.println(abc);
        }
    }
}
